package com.vilynn.learning;

import lombok.Data;

/**
 * Created by Weilin on 2019/10/28.
 * 天壤智能面试题
 * 如果一个单链表为2->1->3->5->4，经过排序后链表结构为1->2->3->4->5，如果只改变链表节点的值，排序无效，需要改变每个节点的引用关系。
 * 思路如下：
 * 1 定义一个辅助节点aux，永远指向链表头结点，即aux.next=head;
 * 2 定义当前节点cur和它的上一个节点pre，如果pre.next<=cur.next,那么pre节点和cur节点同时向后移动
 * 3 如果pre.next>cur.next，切断pre节点和cur节点的引用关系，pre.next=cur.next，把cur节点插入前面恰当位置
 * 4 定义节点 node1=aux和node2=aux.next，同时向后移动node1和node2，当出现cur.val<node2.val时，把cur插入node1和node2之间
 * 5 cur节点变为pre.next
 * ————————————————
 * 版权声明：本文为CSDN博主「ngu_wei」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/zw2008224044/article/details/90713823
 */
@Data
public class Node {
    private boolean isHead;
    private Node next;
    private Integer value;

    public Node(Integer value) {
        this.value = value;
    }

    public Node(Node next, Integer value) {
        this.next = next;
        this.value = value;
    }

    public static Node sort(Node head) {
        if(head==null||head.next==null){
            return head;
        }

        Node pre=head;
        //当前待排序的节点
        Node cur=head.next;
        //辅助节点，永远指向头结点
        Node aux=new Node(0);
        aux.next=head;
        while (cur!=null){
            if(cur.value<pre.value){
                //先把cur节点从当前链表中删除，然后再把cur节点插入到合适位置
                pre.next=cur.next;
                //从前往后找到node2.val>cur.val,然后把cur节点插入到node1和node2之间
                Node node1= aux;
                Node node2=aux.next;
                while (cur.value>node2.value){
                    node1=node2;
                    node2=node2.next;
                }
                //把cur节点插入到node1和node2之间
                node1.next=cur;
                cur.next=node2;
                //cur节点向后移动一位
                cur=pre.next;

            }else {
                //向后移动
                pre=cur;
                cur=cur.next;
            }
        }
        return aux.next;
    }


    public static Node add(Node node1, Node node2){
        Node n0 = sort(node1);
        Node aux = new Node(0);
        aux.next = n0;

        Node curr = node2;
        while (curr != null){
            Node n1 = aux;
            Node n2 = aux.next;
            while (n2 != null && curr.value > n2.value) {
                n1 = n2;
                n2 = n2.next;
            }
            Node temp = curr.next;

            n1.next = curr;
            curr.next = n2;

            curr = temp;
        }

        return aux.next;
    }

    public void print(){
        Node node = this;
        while (node != null) {
            System.out.print(node.value + ", ");
            node = node.next;
        }
        System.out.println();
    }

    public static Node generate(int[] a){
        Node node = null;
        Node temp = node;
        for (int i = 0; i < a.length; i++) {
            if(i == 0){
                node = new Node(a[0]);
                node.setHead(true);
                temp = node;
            }else{
                Node next = new Node(a[i]);
                temp.setNext(next);
                if(i < a.length-1){
                    temp = next;
                }
            }
        }
        return node;
    }

    static final int tableSizeFor(int cap) {
        int MAXIMUM_CAPACITY = 1 << 30;
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    public static void main(String[] args) {

        System.out.println(tableSizeFor(1000));
        System.out.println(tableSizeFor(10000));

//        Node node1 = generate(new int[]{1,4,2,-110,333});
//        Node node2 = generate(new int[]{6,3,-7,223});

//        node1.print();
//        node2.print();
//        Node.add(node1, node2).print();
//        Node.sort(node1).print();
    }
}
